#include <stdio.h>
#include <stdlib.h>
int max(int a, int b);

int main(int argc, char *argv[])
{
  int maxw, n, w, v,i,x;
  scanf("%d%d", &maxw, &n);
  getchar(); // 作为暂停，敲一个键后再继续执行下面的代码
  int *a = (int *)malloc((maxw + 1) * sizeof(int));

  for (i = 0; i < maxw + 1; i++) // a用于记录背包在不同承重下的最大总价值。初始时，将数组中的所有元素初始化为0。
  {
    a[i] = 0;
  }
  for (x = 0; x < n; x++)
{
  scanf("%d%d", &w, &v);
  getchar();
  if (w <= maxw) // 判断物品重量是否超过背包承重
  {
    for (i = maxw; i >= w; i--)
    {
      a[i] = max(a[i], a[i - w] + v);
    }
  }
}

  printf("%d", a[maxw]);
  free(a);//释放动态分配的内存
  return 0;
}
int max(int a, int b)
{
  return (a > b) ? a : b;
}
